package es.ucm.pe.algorithms;

import java.util.ArrayList;


public class AGenetico {
	
	public final static int ID_RULETA = 1;
	public final static int ID_TORNEO = 2;
	public final static int ID_RANKING = 3;
	
	public final static int ID_TERMSIMPLE = 1;
	public final static int ID_FUNCSIMPLE = 2;
	public final static int ID_ARBOL = 3;
	
	private ArrayList<Cromosoma> pob; // poblaci�n
	private int tamPob; // tama�o poblaci�n
	private int numMaxGen; // n�mero m�ximo de generaciones
	private Cromosoma elMejor; // mejor individuo
	private int posMejor; // posici�n del mejor cromosoma
	private double probCruce; // probabilidad de cruce
	private double probMut; // probabilidad de mutaci�n
	private int numGeneracion;
	private int numElite;
	private ArrayList<Cromosoma> elite;
	private double beta;
	private int idSeleccion;
	private int idMutacion;
	private int tamTorneo;
	
	
	public AGenetico(int tamPob,int numMaxGen, double probCruce, double probMut,double percentElitismo, 
			double beta, int idSeleccion, int idMutacion,double valorNTorneo, boolean metodoInic){
		Conjuntos.METODO = metodoInic;
		this.tamPob = tamPob;
		this.numMaxGen = numMaxGen;
		this.probCruce = probCruce;
		this.probMut = probMut;
		this.beta = beta;
		numGeneracion = 0;
		numElite = 0;
		if(percentElitismo>0){
			numElite = (int) ((tamPob*percentElitismo)/100);
		}
		this.idMutacion = idMutacion;
		this.idSeleccion = idSeleccion;
		this.tamTorneo = (int) ((tamPob*valorNTorneo)/100);
		if(tamTorneo<1) tamTorneo = 1;
		
		int[] resultadoCorrecto = new int[20];
		resultadoCorrecto[0] = 1;
		resultadoCorrecto[1] = 1;
		for(int i = 2; i < 20; i++){
			resultadoCorrecto[i] = resultadoCorrecto[i-2] + resultadoCorrecto[i-1];
		}
		Conjuntos.RESULTADO = resultadoCorrecto;
		int valor = 0;
		for(int i = 0; i < resultadoCorrecto.length;i++) {
			valor += resultadoCorrecto[i];
		}
		Conjuntos.SUMA_RESULTADO = valor;
		
	}
	
	public void seleccionRuleta(){
		
		double random = 0;
		int posicionElem;
		ArrayList<Cromosoma> nuevo = new ArrayList<Cromosoma>();

			int tamPobAux = tamPob - numElite;
			for(int i = 0; i < tamPobAux; i++){
				random = Math.random();
				posicionElem = 0;
				while((posicionElem<tamPob-1)&&(random>pob.get(posicionElem).getPuntAcum())){
					posicionElem++;
				}
				nuevo.add(pob.get(posicionElem).clone());
			}
		
		pob = nuevo;
		
	}
	
	public ArrayList<Double> evaluarPoblacion() {//devuelve el valor medio de las aptitudes de la poblacion
		double sumaAptitudes = 0;
		double aptitudElMejor = 0;
		double aptitudMaxima = Integer.MIN_VALUE;
		for(int i = 0; i < pob.size(); i++){
			if(pob.get(i).getAptitud()>aptitudMaxima)
				aptitudMaxima = pob.get(i).getAptitud();
		}
		
		aptitudMaxima = aptitudMaxima*1.05;
		
		aptitudElMejor = Integer.MAX_VALUE;
		
		for(int i = 0; i < pob.size(); i++){
			sumaAptitudes += aptitudMaxima-pob.get(i).getAptitud();
			if(aptitudElMejor>pob.get(i).getAptitud()){
				aptitudElMejor = pob.get(i).getAptitud();
				posMejor = i;
			}
		}
		
		double puntAcum = 0;
		
		for(int i = 0; i < pob.size(); i++){
			pob.get(i).setPuntuacion((aptitudMaxima-pob.get(i).getAptitud())/sumaAptitudes);
			
			puntAcum += pob.get(i).getPuntuacion();
			pob.get(i).setPuntAcum(puntAcum);			
		}
		if(elMejor.getAptitud()>aptitudElMejor){
			elMejor = pob.get(posMejor).clone();
		}
		
		ArrayList<Double> result = new ArrayList<Double>();
		
		if(Math.sqrt(((pob.size()*aptitudMaxima)-sumaAptitudes)/pob.size())>50000){
			result.add(50000.0);
		}else{
			result.add(Math.sqrt(((pob.size()*aptitudMaxima)-sumaAptitudes)/pob.size()));
		}
		
		result.add(Math.sqrt(aptitudElMejor));
		return result;
	}
	
	public void reproduccion(){
		double random = 0;
		ArrayList<Integer> selCruce = new ArrayList<Integer>();
		for (int i = 0; i < tamPob-numElite; i++){
			random = Math.random();
			if(random<probCruce){
				selCruce.add(i);
			}
		}
		if(selCruce.size() % 2 != 0){
			selCruce.remove(selCruce.size()-1);
		}

		ArrayList<Cromosoma> arr;
		for (int i = 0; i < selCruce.size(); i = i + 2){
			arr = cruce(pob.get(selCruce.get(i)),pob.get(selCruce.get(i+1)));
			pob.set(selCruce.get(i), arr.get(0));
			pob.set(selCruce.get(i+1),arr.get(1));
		}
		
	}
	
	public void performRankSelection() {
		ordenaPob();
		ArrayList<Cromosoma> futureParents = new ArrayList<Cromosoma>();
		futureParents.add(pob.get(0).clone());
		futureParents.add(pob.get(1).clone());
		int numOfParents =2;
		double[] fitnessSegments = rankPopulation();
		double entireSegment = fitnessSegments[fitnessSegments.length-1];
		int tamPobAux = tamPob - numElite;
		while(numOfParents<tamPobAux){
			double x = (double)(Math.random()*entireSegment);
			if(x<=fitnessSegments[0]) {
				/*** First Idividual was Selected **/
				futureParents.add(pob.get(0).clone());
				numOfParents++;
			}
			else
				for(int i=1; i<tamPob; i++)
					if(x>fitnessSegments[i-1] && x<=fitnessSegments[i]){
						/*** i'th Idividual was Selected **/
						futureParents.add(pob.get(i).clone());
						numOfParents++;
					}
		} 
		pob = futureParents;
		
	}
	
	private double[] rankPopulation(){
		double[] fitnessSegments = new double[tamPob];
		for(int i=0 ; i<fitnessSegments.length ; i++){
			double probOfIth = (double)i/tamPob;
			probOfIth = probOfIth*2*(beta-1);
			probOfIth = beta - probOfIth;
			probOfIth = (double)probOfIth*((double)1/tamPob);
			if(i!=0)
				fitnessSegments[i] = fitnessSegments[i-1] + probOfIth;
			else
				fitnessSegments[i] = probOfIth;
		}
		return fitnessSegments;
	}
	
	private void ordenaPob() {
		quicksort(pob,0,pob.size()-1);
	}
	
	public void quicksort(ArrayList<Cromosoma> a, int left, int right) {
        if (right <= left) return;
        int i = partition(a, left, right);
        quicksort(a, left, i-1);
        quicksort(a, i+1, right);
    }

    // partition a[left] to a[right], assumes left < right
    private int partition(ArrayList<Cromosoma> a, int left, int right) {
        int i = left - 1;
        int j = right;
        while (true) {
            while (less(a.get(++i), a.get(right)))      // find item on left to swap
                ;                               // a[right] acts as sentinel
            while (less(a.get(right), a.get(--j)))      // find item on right to swap
                if (j == left) break;           // don't go out-of-bounds
            if (i >= j) break;                  // check if pointers cross
            exch(a, i, j);                      // swap two elements into place
        }
        exch(a, i, right);                      // swap with partition element
        return i;
    }

    // is x < y ?
    private boolean less(Cromosoma x, Cromosoma y) {
        return (x.getAptitud() < y.getAptitud());
    }

    // exchange a[i] and a[j]
    private void exch(ArrayList<Cromosoma> a, int i, int j) {
        Cromosoma swap = a.get(i);
        a.set(i,a.get(j));
        a.set(j,swap);
    }
	
    public void seleccionTorneo(){
    	int[] random;//, random2, random3;
    	ArrayList<Cromosoma> nuevo = new ArrayList<Cromosoma>();

    	int tamPobAux = tamPob - numElite;
    	random = new int[tamTorneo];
    	for(int i = 0; i < tamPobAux; i++){
    		for(int j = 0; j < tamTorneo; j++) {
    			
    			random[j] = (int)(Math.random() * (tamPob));
    		}
    		int mejor = random[0];
    		for(int j = 1;j < tamTorneo; j++) {
    			
    			if(pob.get(random[j]).getAptitud() < pob.get(mejor).getAptitud()) {
    				mejor = random[j];
    			}
    		}
    		nuevo.add(pob.get(mejor).clone());
    	}
    	pob = nuevo;
    }
    
	public void mutacion(){
		double random = 0;
		boolean mutado = false;
		Cromosoma c2= null;
		for(int i = 0; i < tamPob-numElite; i++){
			random = Math.random();
			if(random < probMut){
				c2 = mutar(pob.get(i));
				mutado = true;
			}
			if(mutado){
				pob.set(i,c2);
				pob.get(i).evaluar();
				mutado = false;
			}
		}
	}
	
	private Cromosoma mutar(Cromosoma c){
		Cromosoma c2 = null;
		switch(idMutacion){
			case(ID_TERMSIMPLE):{
				c2 = mutacionTermSimple(c);
				break;
			}
			case(ID_FUNCSIMPLE):{
				c2 = mutacionFuncSimple(c);
				break;
			}
			case(ID_ARBOL):{
				c2 = mutacionDeArbol(c);
				break;
			}
		}
		return c2;
	}
	
    
    public Cromosoma mutacionTermSimple(Cromosoma c) {
    	//Cromosoma c = c1.clone();
    	int posMutado = (int)(Math.random()*(c.getListaTerm().size()));
    	int posNuevo = (int)Math.random()*(Conjuntos.TERMINALES.length);
    	c.getListaTerm().get(posMutado).setDato(Conjuntos.TERMINALES[posNuevo]);
    	return c;
    }
    
    public Cromosoma mutacionFuncSimple(Cromosoma c) {
    	//Cromosoma c = c1.clone();
    	int posMutado = (int)(Math.random()*(c.getListaFunc().size()));
    	int posNuevo;
    	if(c.getListaFunc().size()!=0){
	    	do {
	    		posNuevo = (int)(Math.random()*(Conjuntos.FUNCIONES.length));
	    	}
	    	while (c.esUnario(c.getListaFunc().get(posMutado).getDato()) != c.esUnario(Conjuntos.FUNCIONES[posNuevo]));
	    	c.getListaFunc().get(posMutado).setDato(Conjuntos.FUNCIONES[posNuevo]);
    	}
    	return c;
    }
    
    public Cromosoma mutacionDeArbol(Cromosoma c) {
    	//Cromosoma c = c1.clone();    	
    	int pos;
    	AB subArbolElim,subArbolNuevo;
		pos = (int)(Math.random()*(c.getListaFunc().size() + c.getListaTerm().size()));
		if (pos < c.getListaFunc().size()) {
    		subArbolElim = c.getListaFunc().get(pos);
    	}else {
    		subArbolElim = c.getListaTerm().get(pos-c.getListaFunc().size());
    	} 	

    	subArbolNuevo = new AB();
    	if(Conjuntos.METODO){
    		c.inicializarCompleto(subArbolNuevo, subArbolElim.getNivel());
    	}else{
    		c.inicializarCreciente(subArbolNuevo, subArbolElim.getNivel());
    	}
    	if( subArbolElim.getPadre() != null) {
    		if(subArbolElim.esHijoIzq()) {
    			subArbolNuevo.setEsHijoIzq(true);
    			subArbolNuevo.setPadre(subArbolElim.getPadre());
    			subArbolElim.getPadre().setHijoIzq(subArbolNuevo);
    		}
    		else {
    			subArbolNuevo.setEsHijoIzq(false);
    			subArbolNuevo.setPadre(subArbolElim.getPadre());
    			subArbolElim.getPadre().setHijoDch(subArbolNuevo);
    		}
    	}
    	else {
    		c.setGen(subArbolNuevo);
    	}
    	
    	return c;
    }
    
    public ArrayList<Cromosoma> cruce(Cromosoma c1, Cromosoma c2) {
    	//Cromosoma c1 = c1pas.clone();
    	//Cromosoma c2 = c2pas.clone();
    	int numNodos1 = 0;
    	int numNodos2 = 0;
    	int puntoCruce1 = 0;
    	int puntoCruce2 = 0;
    	boolean encontrado = false;
    	AB nodo1 = null;
    	AB nodo2 = null;
    	
    	while(!encontrado){
    		numNodos1 = c1.getListaFunc().size() + c1.getListaTerm().size();
        	numNodos2 = c2.getListaFunc().size() + c2.getListaTerm().size();
        	puntoCruce1 = (int)(Math.random()*(numNodos1));
        	puntoCruce2 = (int)(Math.random()*(numNodos2));
        	
        	if (puntoCruce1 > c1.getListaFunc().size()-1) {
        		nodo1 = c1.getListaTerm().get(puntoCruce1 - c1.getListaFunc().size());
        	}
        	else {
        		nodo1 = c1.getListaFunc().get(puntoCruce1);
        	}
        	if (puntoCruce2 > c2.getListaFunc().size()-1) {
        		nodo2 = c2.getListaTerm().get(puntoCruce2 - c2.getListaFunc().size());
        	}
        	else {
        		nodo2 = c2.getListaFunc().get(puntoCruce2);
        	}
        	if(Conjuntos.METODO){
        		if(nodo1.getNivel() == nodo2.getNivel()){
            		encontrado = true;
            	}
        	}else{
        		int prof1 = nodo1.calcularProfundidad()-1;
        		int prof2 = nodo2.calcularProfundidad()-1;
        		if((nodo1.getNivel() + prof2 <= Conjuntos.PROF_MAXIMA)&&
        				(nodo2.getNivel()+prof1<=Conjuntos.PROF_MAXIMA)){
        			encontrado = true;
        		}
        	}
        	
    	}
	    
    	
    	
    	
    	AB nodoAux;
    	if(!nodo1.esHijoIzq()){//nodo1 es hijo derecho
    		if(nodo1.getPadre()==null){//nodo1 es la raiz
    			c1.setGen(nodo2);
    			nodoAux = nodo2.getPadre();
    			nodo2.setPadre(null);
    			if(nodoAux==null){//nodo2 es la raiz
    				c2.setGen(nodo1);
    			}else{//nodo2 no es la raiz
    				if(nodo2.esHijoIzq()){//nodo2 es hijo izq
    					nodoAux.setHijoIzq(nodo1);
    					nodo1.setPadre(nodoAux);
    					nodo1.setEsHijoIzq(true);
    				}else{//nodo2 es hijo dch
    					nodoAux.setHijoDch(nodo1);
    					nodo1.setPadre(nodoAux);
    					nodo1.setEsHijoIzq(false);
    				}
    			}
    		}else{//nodo1 no es raiz
    			if(nodo2.getPadre()==null) {//nodo 2 es la raiz
    				nodo1.getPadre().setHijoDch(nodo2);
    				nodo2.setPadre(nodo1.getPadre());
    				c2.setGen(nodo1);
    				nodo1.setPadre(null);
    			}else{//nodo2 no es la raiz
    				if(nodo2.esHijoIzq()){//nodo2 es el hijo izq
    					nodo1.getPadre().setHijoDch(nodo2);
    					nodo2.getPadre().setHijoIzq(nodo1);
    					nodoAux = nodo2.getPadre();
    					nodo2.setPadre(nodo1.getPadre());
    					nodo1.setPadre(nodoAux);
    					nodo1.setEsHijoIzq(true);
    					nodo2.setEsHijoIzq(false);
    				}else{ //nodo2 es el hijo derecho
    					nodo1.getPadre().setHijoDch(nodo2);
    					nodo2.getPadre().setHijoDch(nodo1);
    					nodoAux = nodo1.getPadre();
    					nodo1.setPadre(nodo2.getPadre());
    					nodo2.setPadre(nodoAux);
    					nodo1.setEsHijoIzq(false);
    					nodo2.setEsHijoIzq(false);
    				}
    			}
    		}
    	}else{//nodo1 es hijo izquierdo
    		if(nodo1.getPadre()==null){//nodo1 es la raiz
    			c1.setGen(nodo2);
    			nodoAux = nodo2.getPadre();
    			nodo2.setPadre(null);
    			if(nodoAux==null){//nodo2 es la raiz
    				c2.setGen(nodo1);
    			}else{//nodo2 no es la raiz
    				if(nodo2.esHijoIzq()){//nodo2 es hijo izq
    					nodoAux.setHijoIzq(nodo1);
    					nodo1.setPadre(nodoAux);
    					nodo1.setEsHijoIzq(true);
    				}else{//nodo2 es hijo dch
    					nodoAux.setHijoDch(nodo1);
    					nodo1.setPadre(nodoAux);
    					nodo1.setEsHijoIzq(false);
    				}
    			}
    		}else{//nodo1 no es raiz
    			if(nodo2.getPadre()==null) {//nodo 2 es la raiz
    				nodo1.getPadre().setHijoIzq(nodo2);
    				nodo2.setPadre(nodo1.getPadre());
    				nodo2.setEsHijoIzq(true);
    				c2.setGen(nodo1);
    				nodo1.setPadre(null);
    			}else{//nodo2 no es la raiz
    				if(nodo2.esHijoIzq()){//nodo2 es el hijo izq
    					nodo1.getPadre().setHijoIzq(nodo2);
    					nodo2.getPadre().setHijoIzq(nodo1);
    					nodoAux = nodo2.getPadre();
    					nodo2.setPadre(nodo1.getPadre());
    					nodo1.setPadre(nodoAux);
    					nodo1.setEsHijoIzq(true);
    					nodo2.setEsHijoIzq(true);
    				}else{//nodo2 es el hijo derecho
    					nodo1.getPadre().setHijoIzq(nodo2);
    					nodo2.getPadre().setHijoDch(nodo1);
    					nodoAux = nodo1.getPadre();
    					nodo1.setPadre(nodo2.getPadre());
    					nodo2.setPadre(nodoAux);
    					nodo1.setEsHijoIzq(false);
    					nodo2.setEsHijoIzq(true);
    				}
    			}
    		}
    	}
    	
    	c1.getGen().setNiveles(0);
    	c2.getGen().setNiveles(0);
    	ArrayList<Cromosoma> arr = new ArrayList<Cromosoma>();
    	arr.add(c1);
    	arr.add(c2);
    	return arr;
    }
    
	public int getNumGeneracion() {
		return numGeneracion;
	}

	public void setNumGeneracion(int numGeneracion) {
		this.numGeneracion = numGeneracion;
	}
	
	public void increaseNumGeneracion(){
		numGeneracion++;
	}
	
	public void inicializar(){
		pob = new ArrayList<Cromosoma>();
		for(int i = 0; i < tamPob; i++){
			pob.add(new Cromosoma());
		}
		elMejor = pob.get(0);
	}
	
	public void seleccion(){
		switch(idSeleccion){
			case(ID_RULETA):{
				seleccionRuleta();
				break;
			}
			case(ID_TORNEO):{
				seleccionTorneo();
				break;
			}
			case(ID_RANKING):{
				performRankSelection();
				break;
			}
		}
	}
	
	@SuppressWarnings("unchecked")
	public ArrayList resolver(){
		ArrayList result = new ArrayList();
		ArrayList <Double> valoresMedios = new ArrayList<Double>();
		ArrayList<Cromosoma> resultadoMejorIndividuo = new ArrayList<Cromosoma>();
		ArrayList <Double> mejorGeneracion = new ArrayList<Double>();
		ArrayList<Double> evaluacion = null;
		inicializar();
		evaluacion = evaluarPoblacion();
		valoresMedios.add(evaluacion.get(0));
		mejorGeneracion.add(evaluacion.get(1));
		resultadoMejorIndividuo.add(elMejor);
		while(numGeneracion <= numMaxGen){
			numGeneracion++;
			if (numElite != 0) generarElite();
			seleccion();
			reproduccion();
			mutacion();
			if (numElite != 0) insertarElite();
			evaluacion = evaluarPoblacion();
			valoresMedios.add(evaluacion.get(0));
			mejorGeneracion.add(evaluacion.get(1));
			resultadoMejorIndividuo.add(elMejor);
			if(elMejor.getAptitud()==0){
				if(Conjuntos.ABORTAR_OPTIMO){
					break;
				}
			}
		}
		result.add(resultadoMejorIndividuo);
		result.add(valoresMedios);
		result.add(mejorGeneracion);
		return result;
	}
	
	private void generarElite(){
		elite = new ArrayList<Cromosoma>();
		for(int i = 0; i < numElite; i++){
			elite.add(pob.get(i).clone());
		}
		double aptitudMin = 0;
		int pos = -1;
		
		aptitudMin = Integer.MIN_VALUE;
		for(int i = numElite; i < tamPob; i++){
			for(int j = 0; j < numElite; j++){
				if((pob.get(i).getAptitud()<elite.get(j).getAptitud())&&(elite.get(j).getAptitud()>aptitudMin)){
					aptitudMin = elite.get(j).getAptitud();
					pos = j;
				}
			}
			if(pos!=-1){
				elite.remove(pos);
				elite.add(pob.get(i).clone());
				aptitudMin = Integer.MIN_VALUE;
				pos = -1;
			}
		}		
	}
	
	private void insertarElite(){
		for(int i = 0; i < numElite; i++){
			pob.add(elite.get(i));
		}
	}
	
}
